package nestings;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Good solution
 * @author Qu Huanwen
 *
 */
public class Nestings {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Nestings n = new Nestings();
		System.out.println(n.howDeep(""));
		System.out.println(n.howDeep("<(A)(b)>"));
		System.out.println(n.howDeep("(/*/)"));
		System.out.println(n.howDeep("<<<</**/asdf>>>>"));
		System.out.println(n.howDeep("abcd(A(B(C(D)C)B)A)abcd"));
		System.out.println(n.howDeep("([)]"));
		System.out.println(n.howDeep("([{/**/}])"));
		System.out.println(n.howDeep("("));
		System.out.println(n.howDeep("]["));
	}

	private String[] lefts = new String[] { "<", "(", "[", "{", "/*" };
	private String[] rights = new String[] { ">", ")", "]", "}", "*/" };

	public int howDeep(String nested) {
		try {
			List<String> tokens = lex(nested);
			int max = 0;
			Stack<String> stack = new Stack<String>();

			for (String token : tokens) {
				if (token.startsWith("L")) {
					stack.push(token);
					max = Math.max(max, stack.size());
				} else if (token.startsWith("R")) {
					String t = stack.pop();
					if (!t.substring(1).equals(token.substring(1))) {
						throw new Exception("Not match: " + t + ", " + token);
					}
				}
			}
			if (!stack.isEmpty())
				throw new Exception("More lefts.");

			return max;
		} catch (Exception e) {
			return -1;
		}
	}

	private List<String> lex(String input) throws Exception {
		List<String> tokens = new ArrayList<String>();
		int pos = 0;

		whileLoop: while (input.length() > pos) {
			for (int i = 0; i < lefts.length; i++) {
				if (input.startsWith(lefts[i], pos)) {
					tokens.add("L" + i);
					pos += lefts[i].length();
					continue whileLoop;
				} else if (input.startsWith(rights[i], pos)) {
					tokens.add("R" + i);
					pos += rights[i].length();
					continue whileLoop;
				}
			}
			char c = input.charAt(pos);
			if (!Character.isLetter(c)) {
				throw new Exception("Invalid char: " + c);
			}
			pos += 1;
		}
		return tokens;
	}
}
